A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
Identifieur interne : 000055 ( LNCS/Analysis ); précédent : 000054; suivant : 000056A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
Auteurs : Daniel Raible [Allemagne] ; Henning Fernau [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2008.
Abstract
Abstract: In MaxSat, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of ${\mathcal{O}}^*({2^{\frac{K}{6.2158}}})$ for Max-2-Sat (each clause contains at most 2 literals), where K is the number of clauses. The run time has been achieved by using heuristic priorities on the choice of the variable on which we branch. The implementation of these heuristic priorities is rather simple, though they have a significant effect on the run time. Also the analysis uses a non-standard measure.
Url:
DOI: 10.1007/978-3-540-85238-4_45
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001842
- to stream Istex, to step Curation: 001726
- to stream Istex, to step Checkpoint: 000589
- to stream Main, to step Merge: 001277
- to stream Main, to step Curation: 001175
- to stream Main, to step Exploration: 001175
- to stream LNCS, to step Extraction: 000055
Links to Exploration step
ISTEX:9C5537D0EC1486E53D2B4631D5B9DE8D69231B2DLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title><author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/978-3-540-85238-4_45</idno><idno type="url">https://api.istex.fr/document/9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001842</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001842</idno><idno type="wicri:Area/Istex/Curation">001726</idno><idno type="wicri:Area/Istex/Checkpoint">000589</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000589</idno><idno type="wicri:doubleKey">0302-9743:2008:Raible D:a:new:upper</idno><idno type="wicri:Area/Main/Merge">001277</idno><idno type="wicri:Area/Main/Curation">001175</idno><idno type="wicri:Area/Main/Exploration">001175</idno><idno type="wicri:Area/LNCS/Extraction">000055</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title><author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>University of Trier, FB 4—Abteilung Informatik, 54286, Trier</wicri:regionArea><orgName type="university">Université de Trèves</orgName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>University of Trier, FB 4—Abteilung Informatik, 54286, Trier</wicri:regionArea><orgName type="university">Université de Trèves</orgName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2008</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D</idno><idno type="DOI">10.1007/978-3-540-85238-4_45</idno><idno type="ChapterID">45</idno><idno type="ChapterID">Chap45</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In MaxSat, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of ${\mathcal{O}}^*({2^{\frac{K}{6.2158}}})$ for Max-2-Sat (each clause contains at most 2 literals), where K is the number of clauses. The run time has been achieved by using heuristic priorities on the choice of the variable on which we branch. The implementation of these heuristic priorities is rather simple, though they have a significant effect on the run time. Also the analysis uses a non-standard measure.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name></region><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000055 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000055 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= LNCS
|étape= Analysis
|type= RBID
|clé= ISTEX:9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D
|texte= A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
}}
| This area was generated with Dilib version V0.6.31. |  |